package com.xiyou.week05.binarySearch;

/**
 * 410. 分割数组的最大值
 *
 * @ClassName：SplitArray
 * @Author：西柚
 * @Date：2022/1/28 11:01 上午
 * @Versiion：1.0
 */
public class SplitArray {

    /**
     * 输入：nums = [7,2,5,10,8], m = 2
     * 输出：18
     * 解释：
     * 一共有四种方法将 nums 分割为 2 个子数组。
     * 其中最好的方式是将其分为 [7,2,5] 和 [10,8] 。
     * 因为此时这两个子数组各自的和的最大值为18，在所有情况中最小。
     * <p>
     * 链接：https://leetcode-cn.com/problems/split-array-largest-sum
     *
     * @param nums
     * @param m
     * @return
     */
    public int splitArray(int[] nums, int m) {
        int left = 0, right = 0;
        for (int num : nums) {
            left = Math.max(left, num);
            right += num;
        }
        while (left < right) {
            int mid = (left + right) / 2;
            if (validate(nums, m, mid)) {
                right = mid;
            } else {
                left = mid + 1;
            }
        }
        return right;
    }

    private boolean validate(int[] nums, int m, int size) {
        int box = 0;
        int count = 1;
        for (int num : nums) {
            if (box + num <= size) {
                box += num;
            } else {
                count++;
                box = num;
            }
        }
        return count <= m;
    }

    public static void main(String[] args) {
        int[] nums = new int[]{7, 2, 5, 10, 8};
        int m = 2;
        SplitArray splitArray = new SplitArray();
        System.out.println(splitArray.splitArray(nums, m));
    }

}
